package vip.zhenzicheng.algorithm.leetcode.str;

/**
 * <a href="https://leetcode.cn/problems/reverse-words-in-a-string/">颠倒字符串中的单词 [中等]</a>
 *
 * @author zhenzicheng
 * @date 2022-07-26 10:37
 */
public class ReverseWordsInAString_151 {

  public String reverseWords(String s) {
    StringBuilder sb = new StringBuilder();
    int left = 0, right = s.length() - 1;
    char[] charArray = s.toCharArray();

    // 排除前后的空格
    while (left <= right && s.charAt(left) == ' ') {
      left++;
    }
    while (right >= 0 && s.charAt(right) == ' ') {
      right--;
    }

    int lastSpaceIdx;
    while (left <= right) {
      int lastIdx = right;
      while (lastIdx >= left && charArray[lastIdx] != ' ') lastIdx--;
      // 遇见单词前的空格，取出单词[index + 1, right]
      for (int i = lastIdx + 1; i <= right; i++) {
        sb.append(charArray[i]);
      }
      if (lastIdx > left) {
        sb.append(' ');
      }

      // 排除单词间隔中的多个空格
      while (lastIdx >= left && charArray[lastIdx] == ' ') {
        lastIdx--;
      }

      // 重复处理新单词
      right = lastIdx;
    }

    return sb.toString();
  }
}
